package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class FindTheDuplicateNumber {
    // 2022-08-21 12:37:30
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findDuplicate(int[] nums) {
            // 方法实在太多 哈希表、双指针、二分查找
            // 要求，不改数组且不用额外空间
            // 用快慢指针写一版吧,类似环形链表，那如何走两步呢
            int slow = 0, fast = 0;
            while (true) {
                fast = nums[nums[fast]];
                slow = nums[slow];
                if (fast == slow) {
                    break;
                }
            }
            int ans = 0;
            while (true) {
                ans = nums[ans];
                slow = nums[slow];
                if (ans == slow) {
                    break;
                }
            }
            return ans;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}